#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;



//BFS解决拓扑排序1：课程表
class Solution1 {
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) 
    {
        vector<vector<int>> edges(n);
        vector<int> in(n);
        for(int i=0;i<prerequisites.size();i++)
        {
            edges[prerequisites[i][0]].push_back(prerequisites[i][1]);
            in[prerequisites[i][1]]++;
        }
        queue<int> q;
        for(int i=0;i<in.size();i++)
        {
            if(in[i]==0)
                q.push(i);
        }
        while(!q.empty())
        {
            int top=q.front();q.pop();
            for(auto a:edges[top])
            {
                in[a]--;
                if(in[a]==0)    q.push(a);
            }
        }
        int tmp=0;
        for(auto a:in) tmp+=a;
        if(tmp)    return false;
        else return true;
    }
};

//BFS解决拓扑排序2：课程表II
class Solution2 {
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) 
    {
        vector<vector<int>> edges(n);
        vector<int> in(n);
        vector<int> ret;
        for(int i=0;i<prerequisites.size();i++)
        {
            edges[prerequisites[i][0]].push_back(prerequisites[i][1]);
            in[prerequisites[i][1]]++;
        }
        queue<int> q;
        for(int i=0;i<in.size();i++)
        {
            if(in[i]==0)
                q.push(i);
        }
        while(!q.empty())
        {
            int top=q.front();ret.push_back(top);q.pop();
            for(auto a:edges[top])
            {
                in[a]--;
                if(in[a]==0)    q.push(a);
            }
        }
        int tmp=0;
        for(auto a:in) tmp+=a;
        if(tmp)    return {};
        else
        {
            reverse(ret.begin(),ret.end());
            return ret;
        } 
    }
};






int main()
{
    return 0;
}